COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	(DE SAME (X Y) (CHECKEQ (ATOMS X) (ATOMS Y)))
C00005 00003	2.
C00007 00004				420 FINAL
C00009 ENDMK
C⊗;
(DE SAME (X Y) (CHECKEQ (ATOMS X) (ATOMS Y)))

(DE CHECKEQ (X Y)(COND ((NULL X) (IF (NULL Y)
					T
				       NIL))
			((NULL Y) NIL)
			((EQ (FIRST X)(FIRST Y)) (CHECKEQ (REST X) (REST Y)))
			(T NIL)))

(DE ATOMS (X) (IF (ATOM X)
		  (LIST X)
		  (APPEND (ATOMS (LEFT X))
			  (ATOMS (RIGHT X)))))

--------------------------------------------
Define (TIP TR) returning a functional obj F such that:
1. message ATOM sent to F, i.e. (F 'ATOM) -- returns leftmost atom
2. message ALBUT sent to F, i.e. (F 'ALBUT) -- returns remainder of tree.

for example if TR is 		  /\
				 /\ \
				/  \ \
				A   B C

then ((TIP TR) 'ATOM) gives A

and ((TIP TR) 'ALBUT) gives a FUN OBJ (sic) such that
   (((TIP TR) 'ALBUT) 'ATOM) gives B.

NOTE: TIP's FUN OBJ should be a "suspended computation" such that only as much
of TR is expanded as is needed to locate the leftmost atom.

For termination, let TIP return TAF (for That's All Folks) if the tree is empty.

Given TIP, here's SAME:

(DE SAME (TR1 TR2)(SAME* (TIP TR1)(TIP TR2)))

(DE SAME* (F1 F2)((LAMBDA (V1 V2) (COND ((NOT (EQ V1 V2)) NIL)
				        ((EQ V1 'TAF) T)
				        (T (SAME* (F1 'ALBUT) (F2 'ALBUT)))))
		  (F1 'ATOM) (F2 'ATOM)))

It remains to define TIP.

(DE TIP (TR) (STRIP TR (LAMBDA ( ) (LAMBDA (MSG) (CASE MSG
						       (ATOM 'TAF)
						       (T (ERROR)))))))
	
where CASE is like CASEQ except match is against an atom, not a list of atoms.
(the atom T matches anything)

(DE STRIP (TR FN) (IF (ATOM TR)
		      (LAMBDA (MSG) (CASE MSG
					  (ATOM TR)
					  (ALBUT (FN))
					  (T (ERROR))))
		      (STRIP (LEFT TR)
			     (LAMBDA ( )(STRIP (RIGHT TR) FN)))))
2.
			E0
                (FACT 3 (LAMBDA (X) X))
		-----------------------		==>
		FACT | (LAMBDA (N C) ...)

  E1				  E2
 (IF (EQ N 0) ..)		  "  "
------		   ==>		--------		==>
N | 3				N | 2
C | (LAMBDA (X) X):E0		C | (LAMBDA (A)(C (* N A))):E1



  E3				  E4
 "  "				(IF (EQ N 0) ...)
------		   ==>		---------------		==>
N | 1				N | 0
C | (LAMBDA (A)(C (* N A))):E2	C | (LAMBDA (A)(C (* N A))):E3



   =	(C 1)    ==>		(C (* N A))   (access to E3)
				---------
				  A | 1

   =	(C 1)	==>		(C (* N A))   (access to E2)
				-------
				  A | 1


   =	(C 2)	==>		(C (* N A))   (access to E1)
				-------
				  A | 2
				
				  X
  =     (C 6)   =>		-----    => 6
				X | 6
						        
--------------------------------------------
3.

(DE FIRST (X) (X 'FIRST))

(DE CONCAT' (A B)(LAMBDA (MSG) (CASE MSG
				     (FIRST (A))
				     (REST  (B)))))

(DE TERMS' (N) (CONCAT' (LAMBDA ()(DIV 1  (EXPT N 2)))
			(LAMBDA ()(TERMS' (ADD1 N))))))

			420 FINAL

I.What is "functional programming". (approximately 1 hand-written page --
  and if you say "LISP", you  lose; for you have totally missed the point!)

II define	1. object-oriented programming
		2. static scoping
		3. dynamic scoping
		4. call-by-value
		5. functional object

III. relate "object-oriented programming", message-passing programming", and
     "functional programming". differences? similarities?

IV. where (if anywhere) is lexical scoping critical to the correct execution
    of the functional version of SAME.

V. pick the language of your choice and write a non-recursive version of EQUAL,
   a predicate to tell if two binary trees have the same branching structure
   and the same teminal nodes:

(DE EQUAL (X Y)(COND ((ATOM X)(IF (ATOM Y)
				  (EQ X Y)
				   NIL)
		     ((ATOM Y) NIL)
		     ((EQUAL (LEFT X)(LEFT Y)) (EQUAL (RIGHT X)(RIGHT Y)))
		     (T NIL)))



A word to the wise: if you didn't like 420, you won't like the AI course.